A computer system comprising a plurality of processors and a bus system is illustrated in FIG. 1. The computer system 10 comprises a plurality of processors 12 and 14. The processors are divided into two groups, the master processors 12 and the slave processors 14. In general, the master processors 12 communicate to the slave processors 14 particular commands to be carried out. Data is exchanged between the masters and slaves in response to the commands. For example, the master processors 12 generate write commands for writing data into particular slave processors 14. The master processors 12 also generate read commands for reading data from particular slave processors 14. As shown in FIG. 1, a master processor 12 may be a CPU or an I/O controller. A slave processor 14 is typically a memory such as a main memory or a disk memory.
The processors 12 and 14 are interconnected by a bus system 16. The bus system 16 includes an address/command bus 18, a data bus 20, and an arbitration/control bus 22. Illustratively, the address/command bus 18 is shown as comprising separate address and command buses 18a and 18b. Each of the buses 18, 20, 22 may be viewed as comprising a set of wires. The address/command bus 18 is used to transmit commands generated by a master processor 12 to a particular slave processor 14 indicated by an address associated with the command. The data bus 20 is used to exchange data among the master and slave processors in response to commands. The arbitration/control bus 20 is used for handshaking, negotiation, etc. between masters and slaves. In a preferred embodiment, the present invention is applicable to a demultiplexed bus system. In a demultiplexed bus system, the address/command bus 18, the data bus 20, and the arbitration/control bus 22 are physically separate.
As can be seen from FIG. 1, the address/command bus 18 and the data bus 20 are common components which many processors want to use. Thus, an arbitration mechanism is utilized to control access to the buses 18,20 at any given time. Illustratively, the arbitration is carried out by the processors in a distributed manner using the arbitration bus 22. As is described in greater detail below, because the address/command bus and the data bus are physically separate, separate arbitrations are utilized to determine specific processors which gain access to the address/command bus and to the data bus.
The write and read transactions which are carried out by the computer system 10 are now considered in greater detail. A write transaction may be viewed as comprising a write address and command transmitted via the address/command bus and write data transmitted via the data bus. A read transaction comprises a read address and command transmitted via the address/command bus and response data transmitted via the data bus. FIG. 2 shows the timing of some write and read commands on the address/command bus and the corresponding data on the data bus. As can be seen from FIG. 2, in the execution of a write transaction, the write command utilizes the address/command bus and the write data utilizes the data bus almost simultaneously. In contrast, in the execution of a read transaction, there is a delay between the issuing of the read command on the address/command bus and the issuing of the corresponding response data on the data bus. The delay arises because of the time it takes to access a memory to obtain the response data requested by the read command. This kind of transaction is known as a split read transaction. Note, however, that the read responses are maintained in the same order as the read commands, i.e., read command B follows read command A on the address/command bus and read response B follows read response A on the data bus. Thus, the split read responses follow a first-request-first-response order. As is described in greater detail below, the present invention provides an arbitration protocol which enables both write data and split ordered read response data to utilize the data bus in a fair and efficient manner.
FIG. 3 is a Petri-Net like model 30 which illustrates the arbitration process for the computer system 10 of FIG. 1. It should be noted that there are two separate arbitrations, one arbitration for the address/command bus and one arbitration for the data bus. Although these arbitrations may actually be carried out in a distributed fashion at the processors 12,14 themselves through use of the arbitration/control bus 22, in FIG. 3, the address/command bus arbitration is represented by the arbitration machine 32 and the data bus arbitration is represented by the arbitration machine 34.
Requests 36 by different processors 12,14 for access to the address/command bus 18 enter the address/command bus arbitration machine 32. (For purposes of economy the address/command bus is referred to hereinafter as the command bus.) In the schematic diagram of FIG. 3, each of the requests 36 entering the command bus arbitration machine 32 tries to seize the command bus token 38. The command bus arbitration machine 32 will generate one winner at a time.
If the winner is a read transaction, processing is via path 40 and 41. The read command immediately uses the command bus for one or more cycles (e.g., one cycle) to transmit the read command to the memory 43. The command bus is then released as indicated by returning the command bus token via path 41. After a certain memory read latency (recall, read transactions are split transactions), the read response enters a first-request-first-response queue 45 and tries to get on the data bus. The purpose of the first-request-first-response queue 45 is to insure that read responses access the data bus in the same order that read commands access the command bus.
If the winning request at the command bus arbitration machine 32 is a write transaction, processing is via path 50. A winning write transaction does not release the command bus token until getting through the data bus arbitration machine 34. This is because the write transaction uses the command bus to transmit the write command almost simultaneously with using the data bus to transmit the write data (see FIG. 2). Thus, a write transaction holds the command bus token until the data bus is available for the corresponding write data. Accordingly, if write transactions which win the command bus arbitration have to wait a long time to access the data bus, the command bus will be correspondingly blocked from other activities leading to a degradation in command bus bandwidth.
The data bus arbitration machine 34 receives as input requests, requests from the queue 45 to transmit ordered read responses and requests via line 50 to the transmit write data. The data bus arbitration box outputs one winner at a time, which winner may be viewed as seizing a data bus token 52. If a write transaction wins the data bus arbitration, it issues the write command on the command bus and returns the command bus token 38 via path 54. The write data is then transferred via the data bus. This data transfer process is symbolized by 56. In addition, the data bus token 52 is returned. If the winner is a read response, the data bus transfer 56 is applied to the read response data and the data bus token 52 is returned.
The present invention is concerned with the data bus arbitration between the read responses and write data, schematically represented by the machine 34 in FIG. 3. In particular, the present invention is concerned with data bus arbitration between write data and read responses for a system wherein the command and data buses are demultiplexed, wherein read transactions are split transactions, and wherein a first-request-first-response order is maintained for the read responses. Prior art protocols for this situation show unfair favoritism to the read responses over the write data causing bottlenecks in the system.
The prior art data bus arbitration protocol is now considered in greater detail. The prior art data bus protocol is illustratively carried out by one or more finite-state machines located at the individual processors 12,14. (The data bus protocol machine 34 of FIG. 3 schematically represents all of these finite-state machines as well as the arbitration/control bus which connects them.) The prior art data bus protocol makes use of two control signals which are distributed to all processors via the arbitration/control bus. The control signals are DS*, which is asserted if the data bus is not currently available, and RspReqD*, which is asserted when an ordered read response is waiting for the data bus but has not yet achieved access to the data bus.
The protocol is as follows:
a) a processor which is performing a write transaction performs the following command steps: PA1 b) a processor which has a read response which is at the head of a first-request-first-response queue of read responses performs the following command steps: PA1 a) if a processor desires to issue a read command then said processor performs read command steps comprising PA1 b) if a processor desires to perform a write transaction, then the processor performs write transaction steps comprising PA1 c) if a processor desires to provide an ordered split response to a read command and the response is first in a first-request-first-response queue of ordered split read responses, then the processor performs response steps comprising
1) seize or takes control of the command bus (i.e. by winning the command bus arbitration), PA2 2) sample the signals DS* and RspReqD*, PA2 3) if both of these signals are in the dis-asserted state, issue the write command on the command bus, release the command bus, and issue the write data on the data bus, PA2 4) if one or both of these signals is asserted, hold the command bus, and when both are dis-asserted, issue the write command on the command bus, release the command bus, and issue the write data on the data bus; and PA2 1) asserting RspReqD* PA2 2) sampling DS* PA2 3) when DS* is dis-asserted, issuing the response data on the data bus and dis-asserting RspReqD*. PA2 1) seizing or taking control of the command bus (e.g. by winning an arbitration); PA2 2) immediately issuing the read command on the command bus; PA2 1) seizing the command bus (e.g. by winning an arbitration); PA2 2) sampling the signals DS, and RspReqD*; PA2 3) if both DS* and RspReqD* are not in an asserted state, issuing the write command on the command bus, releasing the command bus, and issuing the write data on the data bus; PA2 4) if one, but not both, of DS* and RspReqD* is in the asserted state, holding the command bus and asserting the WReqD*, and after DS* makes a transition from the asserted state to the dis-asserted state, dis-asserting WReqD*, issuing the write command on the command bus, releasing the command bus, and issuing the write data on the data bus; PA2 5) when both DS* and RspReqD* are in the asserted state, holding the command bus and asserting WReqD*, and after DS* makes two transitions from the asserted to the non-asserted state, dis-asserting WreqD*, issuing the write command on the command bus, releasing the command bus, and issuing the write data on the data bus; PA2 1) asserting RspReqD*; PA2 2) sampling DS* and WReqD*; PA2 3) if both DS* and WReqD* are in the dis-asserted state, dis-asserting RspReqD* and issuing the response data on the data bus; PA2 4) if one of DS* and WReqD*, but not both, is in the asserted state, waiting until after DS* makes a transition from the asserted states to the dis-asserted state, then dis-asserting RspReqD*, and issuing the response data on the data bus; PA2 5) if both of DS* and WReqD* are in the asserted state, waiting until after DS* makes two transitions from the asserted to the dis-asserted state, dis-asserting RspReqD* and issuing the response data on the data bus.
This protocol favors the read responses over the write data because any read response which is at the head of queue and ready to issue data can assert RspReqD* which has the effect of blocking write data from access to the data bus. Thus, write data may have to wait for multiple read responses before gaining access to the data bus. This in turn has the effect of tying up the command bus, because a write transaction which gains access to the command bus, does not release the command bus until the corresponding write data gains access to the data bus. Thus, in addition to being unfair to write data, the prior art protocol causes a degradation in command bus bandwidth, and the blocked write can block further read and write requests from sending to memory system.
In view of the foregoing, it is an object of the invention to provide a data bus arbitration procedure which overcomes the problems discussed above.